package chapter3_array;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Created by yuh on 2018/4/8.
 */
public class CountSort {

    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 2};
        countSort1(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void countSort(int[] nums) {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                a++;
            } else if (nums[i] == 1) {
                b++;
            } else {
                c++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i < a) {
                nums[i] = 0;
            } else if (i - a < b) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }

    public static void countSort1(int[] nums) {
        int zero = -1, two = nums.length;
        //三向切分思想 第一个指针开始指向-1  最后面的指针最开始指向最大索引加一
        for (int i = 0; i < two; ) {
            if (nums[i] == 1) {
                //1原地不动
                i++;
            } else if (nums[i] == 2) {
                swap(nums, i, --two);
            } else {
                swap(nums, i++, ++zero);
            }
        }
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
